Clock synchronization in geographically separated devices is an important problem in a wide range of applications ranging from telecommunications to industrial automation. Due to imperfections in clock oscillators and variations in environmental conditions, individual clocks in networked systems invariably drift from one another. One proposed solution to clock drift includes using packet-based methods to synchronize multiple clocks within a network. As shown by FIG. 1, a reference or master clock may be coupled to a slave clock, which must synchronize to the master clock using information transported via an arbitrary packet network. These packet-based methods may utilize timing observations recorded in special packets. For example, according to the IEEE 1588 protocol, timing observations may be made available by two-way exchanges of special “timestamped” packets that are synchronized to a master clock and one or more slave clocks, which must all synchronize to the master clock. While this communication protocol, including the way that timestamped packets are exchanged, is well defined by the IEEE 1588 standard, the actual phase and frequency estimation tasks are only presented for elementary cases (e.g., perfectly symmetrical and fixed transit delay between master and slave devices). The problem of tracking a Master clock over a non-1588 aware network and exhibiting multiple hops and non-stationary traffic, is a challenging problem. In addition to the possible large network packet-delay variation, the clocks themselves typically drift from one another over time, due to imperfections in clock oscillators and variations in environmental conditions. Adding to the complexity of the problem, it is important to achieve synchronization in a timely manner, for many practical reasons, including telecommunication operators' ease of use.
As illustrated by FIG. 2, in one round of two-way exchanges between a master device (“Master”) and a particular slave device (“Slave”), the Master first sends the Slave a packet containing its most accurate reading of the packet departure time T1. The Slave notes in time T2 the reception time of the packet (according to its own slave clock). After an arbitrary amount of time, the Slave responds to the Master with a packet departing at time T3, which the Master stamps at arrival time T4. A packet containing the value of T4 is then sent back to the Slave to complete the exchange. This process may be repeated multiple times, with the variable k indexing N exchange rounds. Accordingly, the Slave may accumulate a set {T1(k), T2(k), T3(k), T4(k)}k=1N of timestamps, from which it must extract information to synchronize to the master clock. As further illustrated by FIG. 2, clock synchronization techniques may also be devised for one-way message dissemination mechanisms.
The information to be extracted can be separated into two components: frequency and time/phase. Frequency synchronization, or “syntonization”, refers to the adjustment of two electronic circuits or devices to operate at the same frequency so that the frequency skew, which is defined as a ratio between Master and Slave frequencies, approaches unity. Relatively few prior art publications address techniques to estimate frequency differences between Master and Slaves, as opposed to estimating the time/phase offset between their clocks. A survey of some recent estimation techniques is provided in an article by III-Keun Rhee et al., entitled “Clock Synchronization in Wireless Sensor Networks: An Overview,” Sensors, Vol. 9 (2009). Additional estimation techniques are disclosed in an article by Kyoung-Lae Noh et al., entitled “Novel Clock Phase Offset and Skew Estimation Using Two-Way Timing Message Exchanges for Wireless Sensor Networks,” IEEE Transactions on Communications, Vol. 55, No. 4, April (2007); and in J. Elson et al., entitled “Fine-grained Network Time Synchronization Using Reference Broadcasts,” Proceedings of the Fifth Symposium on Operating System Design and Implementation, Boston, Mass., December (2002).
One of the most significant applications (in terms of market size) for frequency synchronization is that of mobile base station synchronization. Mobile networks using standards such as GSM, UMTS or LTE all require that each Slave base station is disciplined so as to maintain a certain maximum frequency difference from the Master base station. Typically, the maximum frequency difference must be constrained to an accuracy of ±50 parts per billion (or ppb), so that a frequency ratio between the Master and Slave clocks must be within 1±50×10−9 at the air interface.
A variety of techniques exist for the estimation of frequency skew a for one-way transmissions of timestamps. Due to its simplicity and computational efficiency, one of the most popular techniques consists in using a least-squares linear regression. The resulting Least-Squares (LS) estimate typically coincides with a maximum-likelihood estimate under the assumptions that the packet delay noise is composed of Gaussian independent and identically-distributed random variables. LS-based estimates, which can be fairly robust to Gaussian-like stationary components in the noise process (even with large variance), are also permutation-invariant and robust to packet loss. LS-based estimates will also be accurate provided that the noise-free relationship between T1(k) and T2(k) is indeed linear, and especially provided the packet delay noise does not contain significant “spikes,” which creates outliers. The first condition is relatively simple to satisfy if the observation window length is not too long (i.e. there is no significant drift in the master clock frequency over the observation period). However, the second condition is less likely. For example, in low- to mid-range traffic load disturbances, the noise is far from Gaussian distributed, to the point that the LS estimate may become meaningless. In non-symmetric (non-zero mean included), multi-modal noise statistics, the LS estimate can also be extremely poor.
As disclosed in U.S. Pat. No. 7,051,246 to Benesty, entitled “Method for Estimating Clock Skew Within a Communications Network,” recursive and sequential algorithms such as the Kalman Filter algorithm have also been used to estimate clock skew. However, as described by the '246 patent, the packetization period (i.e., the packet rate of the Master) is considered fixed and ideally accurate, which may not be easy to guarantee in all situations. In addition, U.S. Pat. No. 7,257,133 of Jeske et al., entitled “Method for Estimating Offset For Clocks At Network Elements,” discloses a sufficient statistic (SS) estimator, which may operate as a minimum variance estimator within a class of linear unbiased estimators based on ordered one-way delay measurements.
Additional skew estimating techniques may be based on statistical assumptions and Maximum-Likelihood Estimators (MLE) may be derived accordingly, both in one- and two-way mechanisms contexts. These solutions can be relatively well-performing in relatively low noise conditions, but struggle in more noisy situations. With an exponential distribution assumption for the packet delay noise, the MLE for the skew in a one-way mechanism has also been found to coincide with the solution of a linear programming problem, yielding an estimate that is overall fairly robust and efficient, but may be relatively sensitive to certain types of non-exponential noise (e.g. to Gaussian-like noise). Other algorithms include Paxson's Estimator and the Piecewise Minimum Estimator. Paxson's estimator (devised for one-way data only) partitions the timestamps into non-overlapping subsets, and then uses a Theil-Sen slope estimator on the points corresponding to the minimum delays of all the subsets. This estimator can be fairly robust but typically has certain flaws. First, for large data sets, it can be computationally expensive. Second, for large initial skews, the minima will be biased towards the first or last data points within the timestamps subsets. Moreover, Paxson's estimator, like the Linear Programming algorithm, is not robust to additive Gaussian-like noise. Finally, the Piecewise Minimum Estimator also partitions the stamps into non-overlapping subsets, but then simply connects the minima to form a possibly non-straight line. Notwithstanding these techniques, there continues to be a need for frequency skew estimators that can produce accurate results regardless of the type of packet delay variation statistics (e.g., exponential, Gaussian, skewed, multi-modal, etc.) and approaches the performance of a least-squares (LS) estimator for purely Gaussian noise or Paxson's estimator for purely exponential-noise. There also continues to be a need for techniques that set up skew and/or phase algorithms capable of achieving and maintaining synchronization over arbitrary and possibly changing network traffic, in a well-defined and short period of time (e.g., by minimizing the required N exchange rounds).